#include "main/utils.h"
using namespace std;

void mergeSortIteration(vector<int> &nums) {
  int length = nums.size();
  vector<int> dst(length, 0);
  for (int seg = 1; seg < length; seg += seg) {
    for (int start = 0; start < length; start += seg * 2) {
      int mid = start + seg < length ? start + seg : length;
      int end = start + 2 * seg < length ? start + 2 * seg : length;
      int i = start, j = mid, k = start;
      while (i < mid || j < end) {
        if (j == end || (i < mid && nums[i] < nums[j])) {
          dst[k++] = nums[i++];
        } else {
          dst[k++] = nums[j++];
        }
      }
    }
    nums = dst;
  }
}

void mergeSortCore(vector<int>& nums, int start, int end) {
  if (start + 1 >= end)
    return;

  int mid = (start + end) / 2;
  mergeSortCore(nums, start, mid);
  mergeSortCore(nums, mid, end);

  vector<int> tmp;
  int i = start, j = mid;
  while (i < mid || j < end) {
    if (j == end || (i < mid && nums[i] < nums[j])) {
      tmp.push_back(nums[i++]);
    } else {
      tmp.push_back(nums[j++]);
    }
  }

  int k = 0;
  i = start;
  while (i < end) {
    nums[i++] = tmp[k++];
  }
}

void mergeSortResursive(vector<int>& nums) {
  mergeSortCore(nums, 0, nums.size());
}

int main() {
  vector<int> nums = {4, 6, 2, 8, 0, 1, 3};
  mergeSortIteration(nums);
  printVec("mergeSortIteration", nums);

  vector<int> nums1 = {4, 2, 8, 0, 1, 3, 6};
  mergeSortResursive(nums1);
  printVec("mergeSortResursive", nums1);

  return 0;
}
